import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

/*
给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。

请你找出层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。

输入：[1,7,0,7,-8,null,null]
输出：2
解释：
第 1 层各元素之和为 1，
第 2 层各元素之和为 7 + 0 = 7，
第 3 层各元素之和为 7 + -8 = -1，
所以我们返回第 2 层的层号，它的层内元素之和最大。
 */
class Solution5 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    //层序遍历（广度优先算法）
    public int maxLevelSum(TreeNode root) {
        if(root == null){
            return 0;
        }
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int count = queue.size();

            while (count>0){
                TreeNode cur = queue.poll();
                list.add(cur.val);

                if(cur.left!=null){
                    queue.add(cur.left);
                }
                if (cur.right!=null){
                    queue.add(cur.right);
                }
            }
            res.add(countList(list));
        }
        //比较哪一层最大
        int level = compare(res);
        return level;
    }

    private int countList(List<Integer> list){
        int sum =0;
        for (int i=0;i<list.size();i++){
            sum += list.get(i);
        }
        System.out.println(sum);
        return sum;
    }

    private int compare(List<Integer> list){
        int max = 0;
        int level = 0;
        for (int i=0;i<list.size();i++){
            if(max < list.get(i)){
                max = list.get(i);
                level = i+1;
            }
        }
        return level;
    }

}